package com.leetcode.重建二叉树;

import java.util.Arrays;

/**
 * <p>
 * 参考：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
 * <p>
 * 树遍历的几种方式：https://blog.csdn.net/weixin_41931540/article/details/88957425
 * </p>
 *
 * @author: Sunny
 * @date: 2021/3/11
 * @version: v1.0.0
 */
public class Main {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] b = Arrays.copyOfRange(a, 3, 6);
        for (int value : b) {
            System.out.println(value);
        }

//        int[] pre = {1, 2, 3, 4, 5, 6, 7};
//        int[] in = {3, 2, 4, 1, 6, 5, 7};
//        Main main = new Main();
//        System.out.println(main.reConstructBinaryTree(pre, in));
    }


    /**
     * 因为是树的结构，一般都是用递归来实现。
     * 用数学归纳法的思想就是，假设最后一步，就是root的左右子树都已经重建好了，那么我只要考虑将root的左右子树安上去即可。
     * 根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。
     * 根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，就可以确定好左右子树的范围。
     * 正如上面所说，只需要将确定的左右子树安到root上即可。递归要注意出口，假设最后只有一个元素了，那么就要返回。
     * <p>
     * 树的结果：
     * 1
     * 2   5
     * 3 4 6 7
     * 前序：根左右：1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7
     * 中序：左根右：3 --> 2 --> 4 --> 1 --> 6 --> 5 --> 7
     *
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        //数组长度为0的时候要处理
        if (pre.length == 0) {
            return null;
        }

        // 先序遍历时用的是"根左右"的遍历方式，因此先序遍历第一个节点肯定是root节点
        int rootVal = pre[0];

        //数组长度仅为1的时候就要处理
        if (pre.length == 1) {
            return new TreeNode(rootVal);
        }

        //我们先找到root所在的位置，确定好前序和中序中左子树和右子树序列的范围
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = 0;
        // 根据"root节点+中序遍历"确定根的左子树和根的右子树的范围
        for (int i = 0; i < in.length; i++) {
            if (rootVal == in[i]) {
                rootIndex = i; // rootIndex = i = 3;
                break;
            }
        }

        // 递归，假设root的左右子树都已经构建完毕，那么只要将左右子树安到root左右即可
        // 这里注意Arrays.copyOfRange(int[],start,end)是[)的区间：将原数组进行拷贝到，元素取头不取尾
        // 通过先序遍历找到Arrays.copyOfRange(pre, 1, rootIndex + 1)：作为root左子树的先序遍历值；Arrays.copyOfRange(pre, rootIndex + 1, pre.length)：作为右子树的先序遍历值。
        // 通过中序遍历找到Arrays.copyOfRange(in, 0, rootIndex)：作为root左子树的中序遍历值；Arrays.copyOfRange(in, rootIndex + 1, in.length)：作为右子树的中序遍历值
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndex + 1), Arrays.copyOfRange(in, 0, rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length), Arrays.copyOfRange(in, rootIndex + 1, in.length));

        return root;
    }

}
